A linked storage structure of a linear list is characterized in that, data elements of the linear list are stored by using a group of storage units, and the group of storage units may be or may not be sequential. The linear list is also referred to as a linked list. To represent a logical relationship between each data element ai and a direct successor data element ai+1 of ai, a storage unit that stores the data element ai further needs to store a storage location (also referred to as a pointer) indicating the direct successor data element ai+1 of ai. The two parts of information: the data element ai and the pointer that are stored in the storage unit constitute a node of the data element ai. In the storage unit, a field that stores the data element ai is referred to as a data field, and a field that stores the pointer is referred to as a pointer field. A link (a1, a2, . . . , and an) is formed by linking n nodes (node ai (1≤i≤n)), and a linked list includes multiple links.
The linked list is a set of data storage nodes. The nodes are linked by using pointers, to form a queue. After the linked list is stored in a memory, a dedicated memory is further needed to store management information of each link in the linked list. The dedicated memory is also referred to as a management information memory. Management information of any link includes information such as a head pointer indicating a storage location of a queue head (the first node) of the link, a tail pointer indicating a storage location of a queue tail (the last node) of the link, and a length of the link (a quantity of nodes included in the link).
A physical device to which the memory belongs may process a node in a link in the linked list in the memory. For example, the physical device performs an enqueue operation, that is, the physical device adds a new node to a queue tail of the link; or the physical device performs a dequeue operation, that is, the physical device removes a node from a queue head of the link.
Conventionally, during the enqueue operation of the link in one clock cycle, steps for processing, by the physical device, management information of the link include:
obtaining, by the physical device, an original length of the link;
when the original length is 0, modifying, by the physical device, both a head pointer and a tail pointer of the link; or when the original length is not 0, modifying, by the physical device, only a tail pointer of the link; and
modifying, by the physical device, the length of the link, where a new length obtained after the modification is the original length plus 1.
Conventionally, during the dequeue operation of the link in one clock cycle, steps for processing, by the physical device, management information of the link include:
determining, by the physical device, a total quantity of nodes removed during the dequeue operation;
obtaining, by the physical device, an original length of the link;
determining, by the physical device, a new length of the link, and updating the new length to a management information memory of the link, where the new length is obtained by subtracting the total quantity of removed nodes from the original length; and
when the new length is not 0, modifying, by the physical device, a head pointer of the link; or when the new length is 0, skipping performing, by the physical device, any operation.
To ensure input/output performance of the physical device, the physical device needs to support one enqueue operation and one dequeue operation in one clock cycle. According to the foregoing description, the physical device needs to access and modify the link management information during both the dequeue operation and the enqueue operation, and the management information memory needs to support two reads two writes in one clock cycle. As a result, access overheads of the management information memory are relatively large. The two reads two writes include one read (that is, reading an original length and an original tail pointer of a link) one write (modifying the length and the tail pointer of the link, and further modifying a head pointer when the original length is 0) during the enqueue operation, and one read (reading an original length and an original head pointer of a link) one write (that is, modifying the length and the head pointer of the link) during the dequeue operation.
Because a linked list usually needs to include a huge quantity of links, management information of a link in a management information memory also occupies large space. For example, if there are 1 M (M) links in a linked list stored in a memory in a physical device, and each link can occupy 256 nodes, the management information memory requires at least a depth of 1 M and a bit width of 90 bits (b), that is, the management information memory requires a storage capacity of approximately 90 megabits (Mb).
It can be learned from the foregoing description that the management information memory has a capability of two reads two writes per clock cycle. Therefore, the management information memory needs to have four ports. Because of different quantities of ports that support simultaneous access, implementation costs memories are different. In addition, a larger quantity of ports of a memory indicates larger implementation costs. For example, an area and power consumption of a four-port memory are approximately four times greater than an area and power consumption of a two-port memory. In conclusion, because the management information memory not only needs to have a capability of two reads two writes per clock cycle, but also needs to have a relatively large capacity, costs and power consumption of the management information memory are relatively large.